#!/usr/env/bin python
# -*- coding: utf-8 -*-

# @Time    : 2020-10-16 2:45 下午
# @Author  : yangdy
# @File    : 2020-10-15.116.填充每个节点的下一个右侧节点指针
# @Software: PyCharmCE
from tools.my_methods import *


"""
# Definition for a Node.
"""


class Node:
    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):
        self.val = val
        self.left = left
        self.right = right
        self.next = next


class Solution:
    def connect(self, root: 'Node') -> 'Node':
        que = [root]
        while que:
            new_que = []
            for x in que:
                if not x:
                    continue
                if x.left:
                    new_que.append(x.left)
                if x.right:
                    new_que.append(x.right)
            for i in range(1, len(new_que)):
                new_que[i-1].next = new_que[i]
            que = new_que
        return root
